//循环链表
#ifndef __CIRCULARLINKEDLIST__HPP
#define __CIRCULARLINKEDLIST__HPP

#include"VirtualLinkedList.hpp"

namespace NgSiuKei {

template<class TheClass>
struct circular_linked_list_node {
    TheClass val;
    circular_linked_list_node<TheClass> *prev;
    circular_linked_list_node<TheClass> *next;
};
#define cll_node circular_linked_list_node

template<class TheClass>
class CircularLinkedList: public VirtualLinkedList<TheClass> {
    public:
    CircularLinkedList(void);
    ~CircularLinkedList(void);

    public:
    //清空
    void clear(void);
    //获取特定下标的元素值
    TheClass getVal(const U_L_L &index) const;
    //查找数据，返回下标，表没有则抛出异常：EXCEPTION_CAN_NOT_FIND
    U_L_L findVal(const TheClass &val) const;
    //插入数据
    void insertVal(const TheClass &val, const U_L_L &index);
    //删除特定下标的元素，返回元素值
    TheClass deleteWithIndex(const U_L_L &index);
    //打印表
    void print(void);

    private:
    cll_node<TheClass> *node;
};

template<class TheClass>
CircularLinkedList<TheClass>::CircularLinkedList(void): VirtualLinkedList<TheClass>() {
    this->node = nullptr;
}

template<class TheClass>
CircularLinkedList<TheClass>::~CircularLinkedList(void) {
    this->clear();
}

template<class TheClass>
void CircularLinkedList<TheClass>::clear(void) {
    if(nullptr != this->node) {
        //左右遍历删除
        bool isOddNumber = (0 != this->size%2);//是不是基数
        U_L_L halfSize = this->size/2+((isOddNumber)?(1):(0));
        cll_node<TheClass> *leftNode = this->node->prev;
        cll_node<TheClass> *rightNode = this->node;
        cll_node<TheClass> *currentNode = nullptr;
        for(U_L_L i=0; i<halfSize; ++i) {
            currentNode = leftNode;
            leftNode = leftNode->prev;
            delete currentNode;

            //元素数量为基数时右遍历不需要遍历到最后一个，不然就会delete了野指针
            if(halfSize-1 == i && isOddNumber) {
                break;
            }

            currentNode = rightNode;
            rightNode = rightNode->next;
            delete currentNode;
        }
    }
    this->node = nullptr;
    this->size = 0;
}

template<class TheClass>
TheClass CircularLinkedList<TheClass>::getVal(const U_L_L &index) const {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }
    if(index >= this->size) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }

    cll_node<TheClass> *currentNode = this->node;
    U_L_L step = 0;
    if(index <= this->size/2) {//在前半段
        step = index;
        for(U_L_L i=0; i<step; ++i) {
            currentNode = currentNode->next;
        }
    }
    else {//在后半段
        step = this->size-index;
        for(U_L_L i=0; i<step; ++i) {
            currentNode = currentNode->prev;
        }
    }
    return currentNode->val;
}

template<class TheClass>
U_L_L CircularLinkedList<TheClass>::findVal(const TheClass &val) const {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }

    //左右遍历删除
    bool isOddNumber = (0 != this->size%2);//是不是基数
    U_L_L halfSize = this->size/2+((isOddNumber)?(1):(0));
    cll_node<TheClass> *leftNode = this->node->prev;
    cll_node<TheClass> *rightNode = this->node;
    U_L_L leftIndex = this->size-1;
    U_L_L rightIndex = 0;
    for(U_L_L i=0; i<halfSize; ++i) {
        if(val == leftNode->val) {
            return leftIndex;
        }
        else if(val == rightNode->val) {
            return rightIndex;
        }

        leftNode = leftNode->prev;
        rightNode = rightNode->next;
        leftIndex--;
        rightIndex++;
    }
    throw EXCEPTION_CAN_NOT_FIND;
}

template<class TheClass>
void CircularLinkedList<TheClass>::insertVal(const TheClass &val, const U_L_L &index) {
    if(index > this->size) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }
    
    cll_node<TheClass> *newNode = new cll_node<TheClass>;
    newNode->val = val;

    if(this->isEmpty()) {
        this->node = newNode;
        this->node->next = this->node;
        this->node->prev = this->node;
    }
    else {
        cll_node<TheClass> *currentNode = this->node;
        U_L_L step = 0;
        if(index <= this->size/2) {//在前半段
            step = index;
            for(U_L_L i=0; i<step; ++i) {
                currentNode = currentNode->next;
            }
        }
        else {//在后半段
            step = this->size-index;
            for(U_L_L i=0; i<step; ++i) {
                currentNode = currentNode->prev;
            }
        }
        newNode->next = currentNode;
        newNode->prev = currentNode->prev;
        currentNode->prev->next = newNode;
        currentNode->prev = newNode;
        //如果插入到头里，需要重新调整
        if(0 == index) {
            this->node = newNode;
        }
    }
    this->size++;
}

template<class TheClass>
TheClass CircularLinkedList<TheClass>::deleteWithIndex(const U_L_L &index) {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }
    if(index >= this->size) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }

    cll_node<TheClass> *deleteNode = this->node;
    U_L_L step = 0;
    if(index <= this->size/2) {//在前半段
        step = index;
        for(U_L_L i=0; i<step; ++i) {
            deleteNode = deleteNode->next;
        }
    }
    else {//在后半段
        step = this->size-index;
        for(U_L_L i=0; i<step; ++i) {
            deleteNode = deleteNode->prev;
        }
    }
    deleteNode->prev->next = deleteNode->next;
    deleteNode->next->prev = deleteNode->prev;
    TheClass resultVal = deleteNode->val;
    if(0 == index) {
        this->node = deleteNode->next;
    }
    delete deleteNode;
    this->size--;
    return resultVal;
}

template<class TheClass>
void CircularLinkedList<TheClass>::print(void) {
    cout << "打印循环链表（顺序）：[ ";
    cll_node<TheClass> *currentNode = this->node;
    for(U_L_L i=0; i<this->size; ++i) {
        // cout << '(' << currentNode << " , " << currentNode->val << ") ";
        cout << currentNode->val << ' ';
        currentNode = currentNode->next;
    }
    cout << ']' << endl;

    // cout << "打印循环链表（逆序）：[";
    // currentNode = this->node->prev;
    // for(U_L_L i=0; i<this->size; ++i) {
    //     cout << currentNode->val << ' ';
    //     currentNode = currentNode->prev;
    // }
    // cout << ']' << endl;
}
    
}

#endif